import java.util.*;

/**
 * 957. N 天后的牢房
 * https://leetcode-cn.com/problems/prison-cells-after-n-days/
 */
public class Solutions_957 {
    public static void main(String[] args) {
//        int[] cells = {0, 1, 0, 1, 1, 0, 0, 1};
//        int N = 7;  // output: {0, 0, 1, 1, 0, 0, 0, 0}

        int[] cells = {1, 0, 0, 1, 0, 0, 1, 0};
//        int N = 1000000000;  // output: {0, 0, 1, 1, 1, 1, 1, 0}
        int N = 15;  // output: {0, 0, 0, 1, 0, 0, 1, 0}

        int[] result = prisonAfterNDays(cells, N);
        System.out.println(Arrays.toString(result));
    }

    public static int[] prisonAfterNDays(int[] cells, int N) {
        // map 的键表示第 n 天，值表示第 n 天时的数组状态
        Map<Integer, int[]> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        int[] lastArr = cells;
        // 索引从 [1, N]，方便取余后，从 map 中取值
        for (int i = 1; i <= N; i++) {
            // 获取一天后的状态
            int[] cur = getNext(lastArr);
            String curStr = Arrays.toString(cur);
            if (set.contains(curStr)) {
                // 已经出现过，形成一个周期，周期长度为 set.size()
                break;
            }
            map.put(i, cur);
            set.add(curStr);
            lastArr = cur;
        }
        int loc = N % set.size();
        // 取余
        return map.get(loc == 0 ? set.size() : loc);
    }

    public static int[] getNext(int[] cells) {
        int[] ans = new int[8];
        for (int i = 1; i < 7; i++) {
            // 两个都为 1，或者都为 0 时，异或结果为 0，改变状态为占用
            ans[i] = (cells[i + 1] ^ cells[i - 1]) == 0 ? 1 : 0;
        }
        return ans;
    }
}
